public class Test1 {
    public static void main(String[] args) {
    }
}
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length ;
        int[][] f = new int[len][3] ;
        int[][] g = new int[len][3] ;
        f[0][0] = - prices[0] ;
        f[0][1] = -0x3f3f3f3f ;
        f[0][2] = -0x3f3f3f3f ;
        g[0][1] = -0x3f3f3f3f ;
        g[0][2] = -0x3f3f3f3f ;

        for(int i=1 ; i < len ; i ++){
            for(int j=0 ; j < 3 ; j ++){
                f[i][j] = Math.max(f[i-1][j] , g[i-1][j]-prices[i]) ;
                g[i][j] =  g[i-1][j] ;
                if(j-1>=0){
                    g[i][j] = Math.max(g[i][j] , f[i-1][j-1]+prices[i]) ;
                }
            }
        }
        return Math.max(g[len-1][0] , Math.max(g[len-1][1] , g[len-1][2])) ;

    }
}